//+------------------------------------------------------------------+
//|                                               PrimeGenerator.mqh |
//|                             Copyright 2000-2025, MetaQuotes Ltd. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+

//+------------------------------------------------------------------+
//| CPrimeGenerator 类：素数生成器工具类                              |
//| 核心定位：提供素数相关的工具方法，包括“素数判断”“获取最小素数”“扩展素数”， |
//|           基于预定义素数表+动态计算结合的方式，兼顾效率与通用性       |
//| 核心特性：                                                      |
//|  1. 高效优先：优先使用预定义素数表（包含常用素数），避免重复计算，提升性能； |
//|  2. 动态扩展：当预定义表无法满足需求时，自动动态计算超大素数（支持到 INT_MAX）； |
//|  3. 哈希优化：生成素数时避免与固定哈希基数（101）冲突，适配哈希表容量设计； |
//|  4. 静态工具类：所有方法与成员均为静态，无需实例化即可使用，降低使用成本； |
//| 适用场景：所有需要“素数支撑”的算法与数据结构，典型如：              |
//|  - 哈希表容量设计（素数作为哈希表容量可减少哈希碰撞，提升查找效率）；   |
//|  - 加密算法（素数是 RSA、ECC 等加密算法的核心基础，用于生成密钥对）；   |
//|  - 数学计算（如求最大公约数、素数分解等数论相关场景）；               |
//|  - 数据分片（素数作为分片数量，避免数据分布不均）；                   |
//+------------------------------------------------------------------+
class CPrimeGenerator
  {
private:
   static const int  s_primes[];       // 预定义素数表（包含常用素数，覆盖从小到中的素数范围，用于快速查询）
   static const int  s_hash_prime;     // 哈希优化基数（固定为 101，动态生成素数时需满足 (素数-1) % 101 != 0，避免哈希冲突）

public:
   /**
    * @brief 判断一个整数是否为素数
    * @param candidate [in] 待判断的整数（≥2，小于 2 的数直接返回 false）
    * @return bool - 判断结果：
    *               - true：该数是素数（仅能被 1 和自身整除）；
    *               - false：该数不是素数（存在其他约数）；
    * @note 优化逻辑：
    *       1. 先判断是否为偶数（除 2 外的偶数直接返回 false）；
    *       2. 仅遍历到该数的平方根（大于平方根的约数必然与小于平方根的约数成对出现，减少计算量）；
    *       3. 仅遍历奇数约数（跳过偶数，进一步减少计算量）；
    */
   static bool       IsPrime(const int candidate);

   /**
    * @brief 获取大于等于指定最小值的最小素数
    * @param min [in] 最小素数的下限（≥2，若 min 本身是素数，则直接返回 min）
    * @return int - 结果素数（≥min 的最小素数）
    * @note 执行逻辑（优先级从高到低）：
    *       1. 优先查询预定义素数表 s_primes，返回表中第一个 ≥min 的素数（效率最高）；
    *       2. 若预定义表无满足条件的素数，从 min 开始（若 min 为偶数则+1），依次判断每个奇数是否为素数，直到找到目标素数；
    *       3. 动态生成素数时，需额外满足 (素数-1) % s_hash_prime != 0（适配哈希表容量设计）；
    */
   static int        GetPrime(const int min);

   /**
    * @brief 生成一个大于指定旧值两倍的最小素数（用于动态扩展场景，如哈希表扩容）
    * @param old_size [in] 旧值（≥1，通常为哈希表当前容量、数据规模等）
    * @return int - 扩展后的素数（≥old_size * 2 的最小素数）
    * @note 边界处理：若 old_size * 2 ≥ INT_MAX（整数最大值），则直接返回 INT_MAX（避免溢出）；
    *       核心逻辑：调用 GetPrime(old_size * 2) 实现，本质是 GetPrime 方法的封装，适配“翻倍扩展”场景；
    */
   static int        ExpandPrime(const int old_size);
  };

// 预定义素数表初始化（包含 85 个素数，范围从 3 到 2133142771，覆盖从小到中的常用素数，满足大多数场景的快速查询需求）
const int CPrimeGenerator::s_primes[] =
  {
   3,7,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,
   1103,1327,1597,1931,2333,2801,3371,4049,4861,5839,7013,8419,10103,12143,14591,
   17519,21023,25229,30293,36353,43627,52361,62851,75431,90523,108631,130363,156437,
   187751,225307,270371,324449,389357,467237,560689,672827,807403,968897,1162687,1395263,
   1674319,2009191,2411033,2893249,3471899,4166287,4999559,5999471,7199369,8332579,
   9999161,11998949,14398753,16665163,19998337,23997907,28797523,33330329,39996683,
   47995853,57595063,66660701,79993367,95991737,115190149,133321403,159986773,191983481,
   230380307,266642809,319973567,383966977,460760623,533285671,639947149,767933981,
   921521257,1066571383,1279894313,1535867969,1843042529,2133142771
  };

// 哈希优化基数初始化（固定为 101，该值为常用哈希表基数，动态生成素数时需规避 (素数-1) % 101 == 0 的情况，减少哈希冲突）
const int CPrimeGenerator::s_hash_prime = 101;
//+------------------------------------------------------------------+